/*
 * Copyright 2011-2012 by The Regents of the University of California Licensed
 * under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License. you may obtain a copy of the
 * License from
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package edu.ucsd.db.bassarisk.query.expression.visitor;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

import edu.ucsd.db.bassarisk.exception.SchemaValidationException;
import edu.ucsd.db.bassarisk.exception.VisitorException;
import edu.ucsd.db.bassarisk.query.TransformReturn;
import edu.ucsd.db.bassarisk.query.ValidationTraversalLog;
import edu.ucsd.db.bassarisk.query.binding.ActiveBindings;
import edu.ucsd.db.bassarisk.query.binding.BindingFactory;
import edu.ucsd.db.bassarisk.query.binding.BindingSet;
import edu.ucsd.db.bassarisk.query.binding.Bindings.Binding;
import edu.ucsd.db.bassarisk.query.binding.Bindings.BindingProduct;
import edu.ucsd.db.bassarisk.query.binding.Bindings.BindingUnion;
import edu.ucsd.db.bassarisk.query.binding.Bindings.PositionBinding;
import edu.ucsd.db.bassarisk.query.expression.Expressions;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanAnd;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanNot;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanOr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.Expression;
import edu.ucsd.db.bassarisk.query.expression.Expressions.IBindingExpression;
import edu.ucsd.db.bassarisk.query.expression.Expressions.IStructureConstrainingExpression;
import edu.ucsd.db.bassarisk.query.expression.Expressions.KeywordMatchExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.NonterminalExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.PositionPredExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructureFind;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructureIn;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructurePredExpr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.StructureSame;
import edu.ucsd.db.bassarisk.schema.DataSequenceClass;
import edu.ucsd.db.bassarisk.schema.RunClass;
import edu.ucsd.db.bassarisk.schema.Schema;

public class PositionBindingResolutionTransformation
    extends
    SupertypeDeferingExpressionTreeVisitor<PositionBindingResolutionTransformation.Return, Void> {
  /**
   * Wraps several return values.
   */
  public class Return implements TransformReturn<Expression> {
    /**
     * A data structure recording the top-level bindings available from the
     * expression-sub-tree. Note that any binding that originates under a NOT
     * expression is dead outside the sub-tree rooted at the NOT expression, and
     * any binding that originates under an OR expression is not top-level
     * outside the sub-tree rooted at the OR expression.
     */
    public final ActiveBindings activeBindings;
    /**
     * The expression-sub-tree after transformation.
     */
    private final Expression transformedExpr;

    private Return(final Expression tExpr, final ActiveBindings activeBindings) {
      this.transformedExpr = tExpr;
      this.activeBindings = activeBindings;
    }

    @Override
    public Expression getTransformationRoot() {
      return this.transformedExpr;
    }
  }

  /**
   * Source for new binding objects.
   */
  private final BindingFactory bindingFactory;
  /**
   * All bindings created during the traversal are collected in this object.
   */
  private final BindingSet bindings;
  /**
   * Bindings that are already in place, and non-refineable. Typically this
   * means these are bindings that were created by ancestor expression above a
   * disjunction.
   */
  private final Stack<Binding> establishedBindings;
  /**
   * Bindings that are already in place, and may have their run-classes refined
   * by sub-expressions. Typically these are bindings established by an ancestor
   * expression that is not above a disjunction expression.
   */
  private final Stack<Binding> liveBindings;
  /**
   * Run-classes that ancestor expressions have requested bindings for. Some may
   * be bound already. When creating a new binding, say for a SAME expression,
   * any run-class in this list, but not in the "live" or "established" lists
   * that contains the run-class of the binding to be created must first be
   * created for the sub-expression tree visited.
   */
  private final Stack<RunClass> requestedBindings;
  private final Schema schema;
  /**
   * Records any errors or warnings encountered during the traversal.
   */
  private final ValidationTraversalLog validationArgs;

  public PositionBindingResolutionTransformation(final BindingSet bindings,
                                                 final BindingFactory bindingFactory,
                                                 final Schema schema,
                                                 final ValidationTraversalLog vtl) {
    this.schema = schema;
    this.bindings = bindings;
    this.validationArgs = vtl;
    this.bindingFactory = bindingFactory;
    this.establishedBindings = new Stack<Binding>();
    this.liveBindings = new Stack<Binding>();
    this.requestedBindings = new Stack<RunClass>();
  }

  private boolean isBound(final DataSequenceClass runClass) {
    for (Binding binding : this.establishedBindings) {
      if (binding.boundSequenceClass().getName().equals(runClass.getName())) { return true; }
    }
    for (Binding binding : this.liveBindings) {
      if (binding.boundSequenceClass().getName().equals(runClass.getName())) { return true; }
    }
    return false;
  }

  /**
   * Apply all refinements to a run-class implied by all live and established
   * bound run-classes. <br/>
   * <b>Example:</b> Schema has two classes of elements named "B". One has an
   * ancestor element "A", the other does not. If an outer-expression constrains
   * all matches in this expression to positions within "A", then we can
   * eliminate the subclass of "B" that does not have an ancestor "A".
   * 
   * @throws SchemaValidationException
   */
  private void refineByEstablishedBindings(final DataSequenceClass refinedClass) {
    List<Binding> allEstablished = new ArrayList<Binding>();
    allEstablished.addAll(this.liveBindings);
    allEstablished.addAll(this.establishedBindings);
    for (Binding live : allEstablished) {
      try {
        refinedClass.refineToDescendantsOf(live.boundSequenceClass());
      } catch (SchemaValidationException e) {
        PositionBindingResolutionTransformation.this.validationArgs.addError(e);
      }
    }
  }

  /**
   * Apply refinement to all live bindings that contain a new binding from a
   * sub-expression. <br/>
   * <b>Example:</b> Schema has two classes of elements named "A". One has a
   * descendant element "B", the other does not. If we first bind "A" we bind
   * both classes. If we then also require "B" in a positive sub-expression,
   * then we can refine the binding to "A" to only include the subclass with the
   * "B" descendant.
   * 
   * @throws SchemaValidationException
   */
  private void refineLiveBindings(final DataSequenceClass refiningClass) {
    for (Binding live : this.liveBindings) {
      try {
        live.boundSequenceClass().refineToDescendantsOf(refiningClass);
      } catch (SchemaValidationException e) {
        PositionBindingResolutionTransformation.this.validationArgs.addError(e);
      }
    }
  }

  /**
   * Computes a list of bindings that are required before a specified run-class
   * can be bound and not yet bound. The list is sorted in an appropriate order
   * for applying the bindings.
   */
  private List<RunClass> requiredBindings(final RunClass runClass) {
    Set<RunClass> requiredCandidateSet = new HashSet<RunClass>();
    requiredCandidateSet.addAll(this.requestedBindings);
    for (Binding established : this.establishedBindings) {
      requiredCandidateSet.remove(established.boundSequenceClass());
    }
    for (Binding live : this.liveBindings) {
      requiredCandidateSet.remove(live.boundSequenceClass());
    }
    Comparator<DataSequenceClass> comparitor =
        PositionBindingResolutionTransformation.this.schema
            .sequenceContainmentComparator();
    List<RunClass> requiredList = new ArrayList<RunClass>();
    for (RunClass requiredCandidate : requiredCandidateSet) {
      if (comparitor.compare(requiredCandidate, runClass) > 0) {
        requiredList.add(requiredCandidate);
      }
    }
    Collections.sort(requiredList, comparitor);
    return requiredList;
  }

  /**
   * Helper method to construct a new return object simply.
   */
  private Return
      returns(final Expression tExpr, final ActiveBindings activeBindings) {
    return new Return(tExpr, activeBindings);
  }

  @Override
  public Return visitBooleanAnd(final BooleanAnd expr, final Void arg)
      throws VisitorException {
    List<Expression> subExprs = new ArrayList<Expression>();
    ActiveBindings localActiveBindings = ActiveBindings.createEmpty();
    // Combine the binding sets from all the sub expressions...
    for (Expression subExpr : expr.getSubExprs()) {
      Return subReturn = subExpr.accept(this, null);
      ActiveBindings subActiveBindings = subReturn.activeBindings;
      for (String runClassName : subActiveBindings.getBoundRunClassNames()) {
        localActiveBindings.appendAll(subActiveBindings.getBindings(runClassName));
      }
      subExprs.add(subReturn.transformedExpr);
    }
    return this.returns(expr.transform(subExprs), localActiveBindings);
  }

  @Override
  public Return visitBooleanExpr(final BooleanExpr expr, final Void arg)
      throws VisitorException {
    throw VisitorException.requireSubclassImplementation();
  }

  @Override
  public Return visitBooleanNot(final BooleanNot expr, final Void arg)
      throws VisitorException {
    // Bindings from inside the boolean NOT expression are not propagated up the
    // expression tree.
    // FIXME: Note there is a bug in this; it breaks double negation.
    // For example, the following query will not properly bind keyword
    // 'c' to the WINDOW predicate::
    // <code>WINDOW:3(AND(a NOT(AND(b NOT(c))))</code>
    // This FIXME should be resolved by eliminating nested negation before
    // running the binding resolution visitor.
    Return subExprReturn = expr.getSubExpr().accept(this, null);
    return this.returns(expr.transform(Expressions
        .list(subExprReturn.transformedExpr)), ActiveBindings.createEmpty());
  }

  @Override
  public Return visitBooleanOr(final BooleanOr expr, final Void arg)
      throws VisitorException {
    List<Expression> subExprs = new ArrayList<Expression>();
    ActiveBindings localActiveBindings = ActiveBindings.createEmpty();
    // Any bindings from ancestor expression that were open for refinement are
    // no longer open in sub-expressions. Move from one stack to the other, but
    // remember how many!
    int closedRefinements = this.liveBindings.size();
    for (int i = 0; i < closedRefinements; ++i) {
      this.establishedBindings.push(this.liveBindings.pop());
    }
    // Combine the binding sets from all the sub expressions...
    // This is similar to the algorithm used for visitBooleanAnd, but the
    // differences are called out in the comments.
    for (Expression subExpr : expr.getSubExprs()) {
      Return subReturn = subExpr.accept(this, null);
      ActiveBindings subActiveBindings = subReturn.activeBindings;
      // If there are several bindings from any one disjunct for any one
      // run-class (by name, not by refinement) we combine them into a new
      // product binding.
      for (String runClassName : subActiveBindings.getBoundRunClassNames()) {
        List<Binding> subClassBindings = subActiveBindings.getBindings(runClassName);
        if (subClassBindings.size() > 1) {
          BindingProduct product =
              this.bindingFactory.createProductBinding(subClassBindings);
          expr.putEstablishedBindingProduct(runClassName, subExpr, product);
          localActiveBindings.append(product);
          for (Binding binding : subClassBindings) {
            binding.setParent(product);
          }
        } else if (subClassBindings.size() == 1) {
          localActiveBindings.appendAll(subClassBindings);
        }
      }
      subExprs.add(subReturn.transformedExpr);
    }
    // Create a union binding.
    for (String runClassName : localActiveBindings.getBoundRunClassNames()) {
      List<Binding> classBindings = localActiveBindings.getBindings(runClassName);
      if (classBindings.size() > 0) {
        BindingUnion union = this.bindingFactory.createBindingUnion(classBindings);
        for (Binding binding : classBindings) {
          binding.setParent(union);
        }
        localActiveBindings.clear(runClassName);
        localActiveBindings.append(union);
        expr.putEstablishedBindingUnion(runClassName, union);
      }
    }
    // Return bindings temporarily moved to establishedBindings to the
    // liveBindings stack.
    for (int i = 0; i < closedRefinements; ++i) {
      this.liveBindings.push(this.establishedBindings.pop());
    }
    return this.returns(expr.transform(subExprs), localActiveBindings);
  }

  private Return visitBoundingPositionPredicate(final PositionPredExpr expr,
                                                final Void arg,
                                                final RunClass runClass)
      throws VisitorException {
    if (this.isBound(runClass)) {
      String msg =
          "Constrained run-class '%s' is bound outside the scope of this "
              + "expression. ";
      this.validationArgs.addWarning(expr, String.format(msg, runClass.getName()));
      return expr.getSubExpr().accept(this, null);
    }
    this.requestedBindings.push(runClass);
    Return subReturn = expr.getSubExpr().accept(this, null);
    this.requestedBindings.pop();
    for (Binding binding : subReturn.activeBindings.getBindings(runClass.getName())) {
      expr.addTopLevelBinding(binding);
    }
    return this.returns(expr.transform(Expressions.list(subReturn.transformedExpr)),
                        subReturn.activeBindings);
  }

  @Override
  public Return visitKeywordMatchExpr(final KeywordMatchExpr expr, final Void arg)
      throws VisitorException {
    List<RunClass> openBindingRequirements =
        this.requiredBindings(DataSequenceClass.POSITION_SPACE);
    if (openBindingRequirements.size() > 0) {
      Expression tail = expr;
      for (RunClass runClass : openBindingRequirements) {
        tail = new StructureSame(expr.getInnerExpression(), tail, runClass);
      }
      return tail.accept(this, null);
    } else {
      ActiveBindings activeBindings = ActiveBindings.createEmpty();
      if (expr.isReferenced()) {
        PositionBinding lookupBinding =
            this.bindings.lookupName(expr.getReference());
        if (lookupBinding != null) {
          if (!lookupBinding.getValueFilter().equals(expr.getToken())) {
            String msg = "Reference $%s used for different keyword position sets";
            this.validationArgs.addError(expr,
                                         String.format(msg, expr.getReference()));
          } else {
            activeBindings.append(lookupBinding);
            expr.setEstablishedBinding(lookupBinding);
          }
        } else {
          Binding newBinding =
              this.bindingFactory.createNamedKeywordBinding(expr.getToken(),
                                                            expr.getReference());
          expr.setEstablishedBinding(newBinding);
          activeBindings.append(newBinding);
        }
      } else {
        Binding newBinding =
            this.bindingFactory.createKeywordBinding(expr.getToken());
        expr.setEstablishedBinding(newBinding);
        activeBindings.append(newBinding);
      }
      return this.returns(expr, activeBindings);
    }
  }

  @Override
  public Return visitNonterminalExpr(final NonterminalExpr expr, final Void arg)
      throws VisitorException {
    throw VisitorException.requireSubclassImplementation();
  }

  @Override
  public Return visitPositionPredExpr(final PositionPredExpr expr, final Void arg)
      throws VisitorException {
    RunClass runClass =
        expr instanceof IStructureConstrainingExpression ? ((IStructureConstrainingExpression) expr)
            .getRunClass() : DataSequenceClass.POSITION_SPACE;
    return this.visitBoundingPositionPredicate(expr, arg, runClass);
  }

  @Override
  public Return visitStructureFind(final StructureFind expr, final Void arg)
      throws VisitorException {
    Return subExprReturn = this.visitStuctureAndFind(expr, arg);
    return this.returns(expr.transform(Expressions
        .list(subExprReturn.transformedExpr)), subExprReturn.activeBindings);
  }

  @Override
  public Return visitStructureIn(final StructureIn expr, final Void arg)
      throws VisitorException {
    // In doens't actually provide a binding since the sub expressions below
    // might each bind to a different instance of the run class. Defer
    // binding until a sub-expr that can guarantee the sub-expression-tree
    // should all bind to the same instance.
    this.requestedBindings.push(expr.getRunClass());
    Return subExprReturn = expr.getSubExpr().accept(this, null);
    this.requestedBindings.pop();
    // The only purpose of the in expression is to request those later bindings.
    // The expression is now useless and can be pruned.
    return subExprReturn;
  }

  @Override
  public Return visitStructurePredExpr(final StructurePredExpr expr, final Void arg)
      throws VisitorException {
    throw VisitorException.requireSubclassImplementation();
  }

  @Override
  public Return visitStructureSame(final StructureSame expr, final Void arg)
      throws VisitorException {
    Return subExprReturn = this.visitStuctureAndFind(expr, arg);
    return this.returns(expr.transform(Expressions
        .list(subExprReturn.transformedExpr)), subExprReturn.activeBindings);
  }

  private Return visitStuctureAndFind(final StructurePredExpr expr, final Void arg)
      throws VisitorException {
    // If there are requested bindings for run-classes that contain the run-
    // class specified by this SAME/FIND expression, insert expressions to bind
    // them first!
    List<RunClass> openBindingRequirements =
        this.requiredBindings(expr.getRunClass());
    if (openBindingRequirements.size() > 0) {
      Expression tail = expr;
      for (RunClass runClass : openBindingRequirements) {
        tail = new StructureSame(expr.getInnerExpression(), tail, runClass);
      }
      return tail.accept(this, null);
    } else {
      // The SAME/FIND expression triggers a position binding for the run-class
      // specified by the SAME/FIND expression.
      Binding localBinding =
          this.bindingFactory.createStructureBinding(expr.getRunClass());
      ((IBindingExpression) expr).setEstablishedBinding(localBinding);
      this.refineLiveBindings(expr.getRunClass());
      this.refineByEstablishedBindings(expr.getRunClass());
      this.liveBindings.push(localBinding);
      Return subExprReturn = expr.getSubExpr().accept(this, null);
      this.liveBindings.pop();
      subExprReturn.activeBindings.append(localBinding);
      return subExprReturn;
    }
  }
}
